package DivideAndConquer;

import java.util.Random;

/**
 * 快速排序
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2020/12/16 17:38
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] R = new int[10];
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            R[i] = random.nextInt(101);
        }
        for (int num : R) System.out.print(num + " ");
        System.out.println();

        quickSort(R, 0, 9);
        for (int num : R) System.out.print(num + " ");
    }

    static void quickSort(int[] R, int low, int high) {
        int pivot; // 划分后的基准元素所对应的位置
        if (low < high) { // 仅当区间长度大于1时才需排序
            pivot = partition(R, low, high); // 获取基准元素
            quickSort(R, low, pivot - 1);//对左区间递归排序
            quickSort(R, pivot + 1, high);//对右区间递归排序
        }
    }

    private static int partition(int[] R, int left, int right) {
        int i = left, j = right;
        int key = R[left];//选定枢轴
        while (i < j) {
            while (i < j && R[j] > key)
                --j;
            if (i < j)// 在右子列找到小于key放在左子列
                R[i++] = R[j];

            while (i < j && R[i] < key)
                ++i;
            if (i < j)// 在左子列找到大于key放到右子列
                R[j--] = R[i];
        }
        R[i] = key;//将枢轴插入到R中
        return i;//确定枢轴的位置
    }
}
